package com.nowcoder.code.hjnc;

import java.util.Arrays;
import java.util.HashMap;

public class NC94 {
    Node head = new Node();
    HashMap<Integer, Node> map;
    int size = 0;

    public int[] LFU(int[][] operators, int k) {
        map = new HashMap<>(k);
        int[] result = new int[k];
        int r = 0;
        for (int[] operator : operators) {

            if (operator[0] == 1) {
                Node node;
                if ((node = map.get(operator[1])) != null) {
                    node.val = operator[2];
                    node.time++;

                    Node next = node.next;
                    node.prev.next = next;
                    next.prev = node.prev;
                    while (next.next != null && next.time <= node.time) {
                        next = next.next;
                    }

                    node.next = next.next;
                    node.prev = next;
                    if (node.next != null) {
                        node.next.prev = node;
                    }
                } else {
                    node = new Node();
                    node.val = operator[2];
                    node.time++;

                    Node next = head;
                    while (next.next != null && next.time <= node.time) {
                        next = next.next;
                    }
                    node.next = next.next;
                    node.prev = next;
                    if (node.next != null) {
                        node.next.prev = node;
                    }

                    if (size == k) {
                        map.remove(head.next);
                        head.next = head.next.next;
                        head.next.prev = head;
                    } else {
                        size++;
                        map.put(operator[1], node);
                    }

                }


            } else {
                Node node = map.get(operator[1]);
                if (node == null) {
                    result[r] = -1;
                } else {
                    result[r] = node.val;
                    node.time++;
                    Node next = node.next;
                    node.prev.next = next;
                    next.prev = node.prev;
                    while (next.next != null && next.time <= node.time) {
                        next = next.next;
                    }

                    node.next = next.next;
                    node.prev = next;
                    if (node.next != null) {
                        node.next.prev = node;
                    }
                }
                r++;
            }

        }
        return result;

    }


    private static class Node {

        int val;
        int time;
        Node prev;
        Node next;

    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new NC94().LFU(new int[][]{{1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {1, 2, 4}, {1, 3, 5}, {2, 2}, {1, 4, 4}, {2, 1}}, 3)));
    }


}
